package codeRandomThoughts.Test450删除二叉搜索树中的节点;

import codeRandomThoughts.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return root;

        //二叉搜索树删除节点会遇到5种情况
        //1.没找到删除的节点
        //2.要删除的是叶子结点,直接置空返回
        //3.删除节点的左孩子为空,右孩子替换要删除的节点
        //4.删除节点的右孩子为空,左孩子替换要删除的节点
        //5.左右孩子都不为空,把删除节点的左子树放到删除节点的右子树的最左侧孩子的左孩子中
        if (root.val == key) {
            //2.要删除的是叶子结点,直接置空返回
            if (root.left == null && root.right == null) return null;

            //3.删除节点的左孩子为空,右孩子替换要删除的节点
            if (root.left == null) return root.right;
            //4.删除节点的右孩子为空,左孩子替换要删除的节点
            if (root.right == null) return root.left;

            //5.左右孩子都不为空,把删除节点的左子树放到删除节点的右子树的最左侧孩子的左孩子中
            TreeNode node = root.right;
            while (node.left != null) node = node.left;
            node.left = root.left;
            return root.right;
        }

        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        }
        if (key > root.val) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }
}
